Paper 2019/1391

Are These Pairing Elements Correct? Automated Verification and Applications

Susan Hohenberger and Satyanarayana Vusirikala

Abstract

Using a set of pairing product equations (PPEs) to verify the correctness of an untrusted set of pairing elements with respect to another set of trusted elements has numerous cryptographic applications. These include the design of basic and structure-preserving signature schemes, building oblivious transfer schemes from “blind” IBE, finding new verifiable random functions and keeping the IBE/ABE authority “accountable” to the user. A natural question to ask is: are all trusted-untrusted pairing element groups in the literature PPE testable? We provide original observations demonstrating that the answer is no, and moreover, it can be non-trivial to determine whether or not there exists a set of PPEs that can verify some pairing elements with respect to others. Many IBE schemes have PPE-testable private keys (with respect to the public parameters), while others, such as those based on dual-system encryption, provably do not. To aid those wishing to use PPE-based element verification in their cryptosystems, we devised rules to systematically search for a set of PPEs that can verify untrusted elements with respect to a set of trusted elements. We prove the correctness of each rule and combine them into a main searching algorithm for which we also prove correctness. We implemented this algorithm in a new software tool, called AutoPPE. Tested on over two dozen case studies, AutoPPE found a set of PPEs (on schemes where they exist) usually in just a matter of seconds. This work represents an important step towards the larger goal of improving the speed and accuracy of pairing-based cryptographic design via computer automation.

Metadata
Available format(s)
PDF
Category
Applications
Publication info
Published elsewhere. Minor revision. ACM CCS 2019
DOI
10.1145/3319535.3339808
Keywords
formal analysisautomating crypto
Contact author(s)
susan @ cs jhu edu
satya @ cs utexas edu
History
2019-12-04: received
Short URL
https://ia.cr/2019/1391
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/1391,
      author = {Susan Hohenberger and Satyanarayana Vusirikala},
      title = {Are These Pairing Elements Correct? Automated Verification and Applications},
      howpublished = {Cryptology {ePrint} Archive, Paper 2019/1391},
      year = {2019},
      doi = {10.1145/3319535.3339808},
      url = {https://eprint.iacr.org/2019/1391}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.